00100	AN OBVIOUS PROBLEM WITH EDGE FINDERS OCCURS NEAR CORNERS.
00200	AN EDGE FINDER DESIGNED FOR ISOLATED EDGES HAS BIG PROBLEMS
00300	NEAR CORNERS AND HAS SOME OF MANY POSSIBLE FAULTS.  THESE
00400	INCLUDE:
00500		EXTENSION PAST CORNERS
00600		DEFORMATION OF EDGES AT CORNERS
00700		CUTTING OFF EDGES AT CORNERS
00800	
00900	POSSIBLE CURES:
01000		TREAT THIN LINES AS ANOTHER PRIMITIVE, AND
01100			BY SOME COMPLEX PROCESS, MATCH THE TWO MERGED
01200			EDGES WITH THE TERMINATING CORNER
01300		CHOOSE THE BEST DIRECTION TO AVOID INTERFERENCE OF
01400			EDGES AND PROCEED WITHOUT REGARD FOR CORNERS
01500		FIT A CORNER TEMPLATE
01600	
01605		GET HIGHER RESOLUTION AS BY MY SCHEME
     

00100		LOCALIZATION CAN BE DONE IN SEVERAL WAYS.  WE 
00200	WANT NOW TO DISCUSS PREFERENCE AMONG THESE SCHEMES.
00300		1  MAXIMUM OF GRADIENT
00400		THIS WORKS IF THE STEP IS SHARP COMPARED TO THE
00500		INTERVAL OF INTEGRATION.  OTHERWISE, THE RESULT
00600		IS A BROAD FLAT PLATEAU, AND THE MAX OF THE GRADIENT
00700		IS NOT WELL DEFINED, LOCALIZATION IS POOR
00800	
00900		2  MAXIMUM OF CORRELATION GRADIENT
01000		THIS IS ESSENTIALLY THE SAME AS THE GRADIENT, AND
01100		THE SAME REMARKS APPLY
01200	
01300		3  CENTROID OF THE GRADIENT
01400		THIS IS NEARLY EQUIVALENT TO THE CUTOFF AT THE 
01500		VALUE MIDWAY BETWEEN THE TWO EXTREMES.  WHEN THE STEP
01600		IS NARROW, IT TENDS TOWARD THE MAXIMUM OF THE GRADIENT,
01700		AND WHEN THE STEP IS WIDE, IT REMAINS NEAR THE CENTER
01800		OF THE INTERVAL.
01900	
     

00100		Visual processing has progressed more slowly 
00200	than we had hoped.  Our scene description routines currently 
00300	are weak at recognizing boundaries in visual scenes.
00400	One attitude is that it is impossible to do better without
00500	elaborate use of context.  Another is that it is unnecessary
00600	to do better, because very sophisticated and elaborate
00700	use of context will suffice for problems such as have been
00800	attempted.  Whether it is possible to improve
00900	finding of boundaries is a question which can be answeredλd
01000	analytically at some later time when the probe
01100	is better understood.  
01200	At present, facilities and ideas for context are quite pri
01300	primitive and improved boundary detection would lessen theλ
01400	burden on these techniques of using context.
01500		the primary problems in recognizing boundaries
01600	are not really trivial:
01700	
01800	
01900	
02000	
     

00100		1.  W
00105	
00110	
00115		1. We must detect a variety of boundary types.  Discontinuities
00120		appear not only as steps, but as delta functions and slope
00125		discontinuities and combinations of these.  Two treatments have
00130		attempted to enumerate the types of features [hHerskovits,
00135		Griffith].  An operator which looks only for steps would miss
00140		thin lines on a surface.
00145	
00150		2.  
00155	
00160		2.  We must detect a second-derivative like function at 
00165		boundaries, because large constant gradients are very common
00170		with curved surfaces or where there are strong reflections,
00175		as with any stack of blocks.  Consequently, gradient operators
00180		become confused and identify an entire region as edge points.
00185		This is also a problem for operators which fit a step unless the
00190		support is quite large, because there is little difference between
00195		the chi-squared fit of a small step or equivalent constant gradient
00200		(where small step means of the order of the noise in intensity).
00205	
00210		3.
00215		Localization of a discontinuity within the support of the operator
00220		is necessary, because an operator averages over a broad area of 
00225		support.  The value of the operator exceeds cutoff over a range
00230		of position and angle.  
00235		The properties of the localization are not useually considered
00240		at all; taking a maximum is a usual procedure.
00245	
00250		4.  The resolution of small spatial features (or nearby parallel
00255		lines should be near the sensor resolution.  `ltimate resolution
00260		is limited by contrast; with high contrast we can resolve the 
00265		full camera resolution.  Lower contrast requires larger support.
00270		For a human body, many small features on the face are important
00275		for recognition. An intermediate standard of resolution would 
00280		be to detect long thin features with high resolution.
00285	
00290		5.  Global organization of line segments is an integral part
00295		of the analysis of boundary finding.  A local operator generates
00300		line segments which are locally significant, according to its
00305		short-sighted view.  The sensitivtiy of an overall process depends
00310		strongly on how the line segments are turned into lines.  Line
00315		segments from a local operator can be regarded as local hypotheses.  
00320		On a slightly more global scale of organization, these hypotheses
00325		predict nearby intensity values and imply condition on nearby
00330		line segments to be connected.  
00335		The strongest conditions are continuity in intensity and direction. 
00340	e
01570	
01600		
01700		6.  Self-normalization for noise.  Detector noise can be estimated
01800		from a simple model of the detector and its state of operation.	
01900		Thresholds can be calculated simply for detection in the presence
02000		of only Gaussian detector noise of known amplitude.  
02100		In interesting cases, the surfaces are far from homogeneous and
02200		the surface irregularities at a micro scale can be regarded as 
02300		another population of noise, ie too small to have spatial
02400		continuity.  The detection process should be able to be relatively
02500		insensitive to surface noise far in excess of the detector noise.
02600		
02700		7. Sensitivity must be good enough to find many of the boundaries.
02800		Some discussions of sensitivity assume that sensitivity can be
02900		arbitrarily increased by lowering thresholds.  We define sensitivity
03000		as the minimum signal detectable with reasonable probability
03100		(say 50%) for a given noise level (1%, for example).
03200		The overall sensitivity of a process depends not only on the 
03300		sensitivity of a local operator, but also on the subsequent 
03400		organization fo those line segments.  We can determine sensitivity
03500		of local operators by analysis.  Although we don't have a formalism
03600		for choice of an optimum technique, (largely because we have
03700		no adequately precise formalism for defining the conditions for 
03800		optimality) we can look at a well-defined process and make accurate
03900		analytic estimates of its sensitivity.
04000	
04100	
04200	
04300	
04400		We are primarily interested in techniques which will function
04500	with curved objects with fairly uniform surfaces.  We cannot yet handle
04600	much texture, although a reasonable amount can be simply ignored by
04700	strong continuity requirements on organization of edges.
04800	
04900		In what follows, a good model for  noise is that there are two
05000	populations, detector noise and surface blemishes.  Detector noise has
05100	has known spectrum, while surface blemishes may be arbitrary, but have 
05200	infrequent (1%)
     

00100		We discuss some previous techniques for boundary detection
00200		in view of the requirements we have stated.  We begin with
00300	a discussion of local operators and later compare methods of organization.
00350	We later discuss some techniques which improve performance according
00355	to those standards and describe implementations of those techniques.
00360	We discuss error calculations in detail in an appendix.
00400	l.  Gradient operators:
00500		The examples of these operators (Robert's cross [Roberts],
00600	Sobel's operator [Pingle), and coincidence predicates [Binford])
00700	are defined over a small support, 2x2 or 3x3.  Their sensitivity is
00800	inadequate, but even with this low sensitivity, in one of the 
00900	experiments, reflections often caused such large gradients that 
01000	whole faces were seen as full of edge points.  Clearly there is no gain
01100	in using gradient operators with larger support, since their
01200	utility is limited by undesirable sensitivity to constant slopes.
05300	
05305	2.  Second-derivative and third-derivative operators
05310	Herskovits has used second and third derivative operators
05315	to detect step, slope, and delta function discontinuities
05320	in edge verification.  The global organization used enabled
05325	high sensitivity.  Since these operators are insensitive to
05330	constant slopes, the area of support was made large to 
05335	enhance sensitivity, at the expense of resolution of small
05340	features and crowded areas.  The system could handle a considerable
05345	amount of texture.
05350	
05355	
05360	3.  Operators which fit a step.
05365	Hueckel [Hueckel) fits a step function to a domain by parameterizing
05370	a step position and orientation in terms of low-order Fourier 
05375	components.  A goodness of fit is calculated.  The claim is that
05380	the low-frequencies contain the signal and the high frequencies 
05385	contain noise.  At an edge, there is considerable high frequency
05390	signal, and to the extent that it is filtered out, sensitivity 
05395	suffers, and undesirable sensitivity to constant gradients is
05400	emphasized by smearing the distinction.  In our own work, discussed
05405	later, using an operator which fit a step exactly, we encountered
05410	serious problems with reflections and with curved surfaces.
05415	A qualitative evaluation of the claim for low-frequency filtering
05420	is to visually inspect the results of low-pass and high-pass
05425	filtering.  High pass filtering leaves an image almost as good
05430	visually as unprocessed, and in some cases of limited dynamic
05435	range of the recording medium, gives enhancement.  Low pass filtering
05440	severely degrades an image visually.
05445	
05450	4.  Template Operators
05455	Griffith [Griffith] has implemented a scheme using a zoo of about 
05460	10 templates which are correlated with the video signal at points
05465	along a scan line.  The quality of fit is tested and a bbest fit is taken
05470	as a candidate if the correlated signal is above threshold.
     

00000	
00100	TO FIT CURVES TO BOUNDARIES IN THE PLANE:
00200		USE A TWO STAGE SCHEME
00300	
00400		FIRST, TAKE PROJECTIONS AT A FEW ANGLES, FIND
00500		LOCAL EXTREMA BY AN ARRAY (ONE-DIMENSIONAL)
00550		, A PDL IS ALL THAT IS NECESSARY,
00600		WHICH IS LABELLED BY POINTS PASSING OVER.
00700		AN EXTREMUM CAN BE INVESTIGATED BY LOCAL APPROX
00800		OR BY CALCULATION OF THE DIFFERENCE IN ARC LENGTH
00900		AND SAGITTA BETWEEN THE TWO POINTS.  
01000		FOR AN EXTREMUM WHICH IS ALSO A CORNER, THE EXTREMUM
01100		IS STABLE UNDER ROTATIONS (THE FORWARD AND BACKWARD
01200		TANGENTS ARE AT 180 DEGREES FOR SMOOTH CURVES; THE
01300		EXTREMUM IS STABLE FOR A RANGE OF ANGLES BETWEEN
01400		TANF-TANB AND PI.)
01500	
01600		SMALL ANGLE CORNERS WILL BE MISSED BY THIS PROCESS.
01700		HOWEVER, WE CAN USE A SECOND STAGE PROCEDURE WHICH
01800		HAS ALREADY BEEN USED FOR STRAIGHT LINE SEGMENTATION.
01900		THAT PROCEDURE IS TO PROJECT AT ANGLES AROUND THE
02000		THE DIRECTION OF THE LINE BETWEEN ENDPOINTS.  
02100		THE EXTREMA CAN BE TESTED FOR DISCONTINUITY.
02200